题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2844
数据生成器:http://paste.ubuntu.com/23312434/
话说这个题啊!还是挺有意思哒!
有一个结论:如果相同的数要计入答案的话,那每种答案出现了2^(n-线性基的数量)
证明:既然都为0了,那么取不取都不影响答案,于是可以随便搞一搞
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 10086; const int N = 100000+9; const int SGZ = 30+9; int n,m,arr[N],bas[SGZ],cnt,vout; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline bool insert(int w) { for (int i=30;~i;i--) if (w&(1<<i)) { if (bas[i]) { w ^= bas[i]; } else { bas[i] = w; return true; } } return false; } inline int pow(int w , int t) { int ret = 1; while (t) { if (t&1) ret = (LL)ret * w % MOD; w = (LL)w * w % MOD; t >>= 1; } return ret; } int main(){ n = read(); for (int i=1;i<=n;i++) { arr[i] = read(); cnt += insert(arr[i]); } m = read(); for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) { cnt--; if (m&(1<<i)) { vout += tmp * (1LL<<cnt) % MOD; vout %= MOD; } } printf("%d\n",(vout+1)%MOD); return 0; }
I like this web site very much so much wonderful information.
You have mentioned very interesting details! ps nice website . “Mediocrity knows nothing higher than itself, but talent instantly recognizes genius.” by Conan Doyle.